{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Values From Labels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestValsFromLabels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #受标签影响的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们有一个&nbsp;<code>n</code>&nbsp;项的集合。给出两个整数数组&nbsp;<code>values</code>&nbsp;和 <code>labels</code>&nbsp;，第 <code>i</code> 个元素的值和标签分别是&nbsp;<code>values[i]</code>&nbsp;和&nbsp;<code>labels[i]</code>。还会给出两个整数&nbsp;<code>numWanted</code>&nbsp;和 <code>useLimit</code> 。</p>\n",
    "\n",
    "<p>从 <code>n</code> 个元素中选择一个子集 <code>s</code> :</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子集 <code>s</code> 的大小&nbsp;<strong>小于或等于</strong> <code>numWanted</code> 。</li>\n",
    "\t<li><code>s</code> 中 <strong>最多</strong> 有相同标签的 <code>useLimit</code> 项。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一个子集的&nbsp;<strong>分数&nbsp;</strong>是该子集的值之和。</p>\n",
    "\n",
    "<p>返回子集&nbsp;<code>s</code> 的最大 <strong>分数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>选出的子集是第一项，第三项和第五项。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>选出的子集是第一项，第二项和第三项。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>选出的子集是第一项和第四项。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == values.length == labels.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= values[i], labels[i] &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= numWanted, useLimit &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-values-from-labels](https://leetcode.cn/problems/largest-values-from-labels/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-values-from-labels](https://leetcode.cn/problems/largest-values-from-labels/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,3,2,1]\\n[1,1,2,2,3]\\n3\\n1', '[5,4,3,2,1]\\n[1,3,3,3,2]\\n3\\n2', '[9,8,8,7,6]\\n[0,0,0,1,1]\\n3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        d = dict()\n",
    "        for i in range(len(values)):\n",
    "            d[labels[i]] = d.get(labels[i], []) +[values[i],]\n",
    "        for k in d.keys():\n",
    "            d[k].sort(reverse=True)\n",
    "            d[k] = d[k][:useLimit]\n",
    "        z = []\n",
    "        for k in d.keys():\n",
    "            for num in d[k]:\n",
    "                if len(z)<numWanted:\n",
    "                    z.append(num)\n",
    "                    if len(z)==numWanted:\n",
    "                        z.sort(reverse=True)\n",
    "                else:\n",
    "                    for i in range(numWanted):\n",
    "                        if z[i]<num:\n",
    "                            z.append(num)\n",
    "                            z.sort(reverse=True)\n",
    "                            z = z[:numWanted]\n",
    "                            break\n",
    "        return sum(z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ls = []\n",
    "        for x, y in zip(values, labels):\n",
    "            ls.append((x, y))\n",
    "        ls.sort(key=lambda x: x[0], reverse=True)\n",
    "        ans = 0\n",
    "        cnt = dict()\n",
    "        i = 0\n",
    "        for x, y in ls:\n",
    "            if y not in cnt.keys():\n",
    "                cnt[y] = 1\n",
    "            else:\n",
    "                cnt[y] += 1\n",
    "            if cnt[y] <= useLimit:\n",
    "                ans += x\n",
    "                i += 1\n",
    "            if i >= numWanted:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = list(range(len(values)))\n",
    "        n.sort(key=lambda x:values[x],reverse=True)\n",
    "        # 每一组拿了多少个\n",
    "        curGroupPicked = Counter()\n",
    "        # 当前拿了的个数\n",
    "        picked = 0\n",
    "        # 当前的value总和\n",
    "        res = 0\n",
    "        for i in n:\n",
    "            # 从大到小去取，如果当前label的数量超标就不取这一个\n",
    "            if curGroupPicked[labels[i]]>=useLimit:\n",
    "                continue\n",
    "            curGroupPicked[labels[i]]+=1\n",
    "            res+=values[i]\n",
    "            picked+=1\n",
    "            if picked==numWanted:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        n = len(values)\n",
    "        self.quickSort(values, labels, 0, n - 1)\n",
    "        cnt = collections.Counter()\n",
    "        while numWanted and i < n:\n",
    "            while cnt[labels[i]] == useLimit:\n",
    "                i += 1\n",
    "                if i == n:\n",
    "                    return ans\n",
    "            ans += values[i]\n",
    "            cnt[labels[i]] += 1\n",
    "            i += 1\n",
    "            numWanted -= 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def quickSort(self, values, labels, left, right):\n",
    "        if left >= right:\n",
    "            return\n",
    "        l, r = left, right\n",
    "        c = values[left]\n",
    "        lt = labels[left]\n",
    "        while l < r:\n",
    "            while l < r and values[r] <= c:\n",
    "                r -= 1\n",
    "            if l < r:\n",
    "                values[l] = values[r]\n",
    "                labels[l] = labels[r]\n",
    "                l += 1\n",
    "            while l < r and values[l] >= c:\n",
    "                l += 1\n",
    "            if l < r:\n",
    "                values[r] = values[l]\n",
    "                labels[r] = labels[l]\n",
    "                r -= 1\n",
    "\n",
    "        values[l] = c\n",
    "        labels[l] = lt\n",
    "        self.quickSort(values, labels, left, l - 1)\n",
    "        self.quickSort(values, labels, l + 1, right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: list[int], labels: list[int], numWanted: int, useLimit: int) -> int:\n",
    "        sorted_range = sorted(range(len(values)), key=lambda x: -values[x])\n",
    "        output = 0\n",
    "        count_list = []\n",
    "        number_count = 0\n",
    "        for item in sorted_range:\n",
    "            max_labels = count_list.count(labels[item])\n",
    "            if max_labels < useLimit:\n",
    "                output += values[item]\n",
    "                count_list.append(labels[item])\n",
    "                number_count += 1\n",
    "            if number_count == numWanted: break\n",
    "        return(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        def quick_sort(nums, indexs, left, right):\n",
    "            L = left\n",
    "            R = right\n",
    "            first_element = nums[L]\n",
    "            first_index = indexs[L]\n",
    "            while(left<right):\n",
    "                while(left<right and nums[right] >= first_element):\n",
    "                    right -= 1\n",
    "                while(left<right and nums[left] <= first_element):\n",
    "                    left += 1\n",
    "                tmp = nums[left]\n",
    "                tmp1 = indexs[left]\n",
    "                nums[left] = nums[right]\n",
    "                nums[right] = tmp\n",
    "                indexs[left] = indexs[right]\n",
    "                indexs[right] = tmp1\n",
    "            nums[L] = nums[left]\n",
    "            nums[left] = first_element\n",
    "            indexs[L] = indexs[left]\n",
    "            indexs[left] = first_index\n",
    "            if right < len(nums) - 1 and R > right:\n",
    "                nums,indexs = quick_sort(nums,indexs,right+1,R)\n",
    "            if right > 0 and L < right:\n",
    "                nums,indexs = quick_sort(nums,indexs,L,right-1)\n",
    "            return nums,indexs\n",
    "\n",
    "        values,labels = quick_sort(values,labels,0,len(values)-1)\n",
    "        dict_res = {}\n",
    "        n = len(values)\n",
    "        res = 0\n",
    "        elementNum = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if labels[i] not in dict_res:\n",
    "                dict_res[labels[i]] = 1\n",
    "                res += values[i]\n",
    "                elementNum += 1\n",
    "            else:\n",
    "                if dict_res[labels[i]] == useLimit:\n",
    "                    continue\n",
    "                else:\n",
    "                    print(i)\n",
    "                    dict_res[labels[i]] += 1\n",
    "                    res += values[i]\n",
    "                    elementNum += 1\n",
    "            if elementNum == numWanted:\n",
    "                break\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        hash_map={}\n",
    "        n=len(values)\n",
    "        for i in range(n):\n",
    "            if labels[i] not in hash_map:\n",
    "                hash_map[labels[i]]=[values[i]]\n",
    "            else:\n",
    "                if len(hash_map[labels[i]])<useLimit:\n",
    "                    hash_map[labels[i]].append(values[i])\n",
    "                else:\n",
    "                    temp=min(hash_map[labels[i]])\n",
    "                    if values[i]>temp:\n",
    "                        to_rep=hash_map[labels[i]].index(temp)\n",
    "                        hash_map[labels[i]][to_rep]=values[i]\n",
    "        ans=[]\n",
    "        for i in hash_map:\n",
    "            for j in hash_map[i]:\n",
    "                ans.append(j)\n",
    "        ans.sort(reverse=True)\n",
    "        return sum(ans[:numWanted])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        dd = {n:[] for n in labels}\n",
    "        for i in range(len(labels)):\n",
    "            dd[labels[i]].append(values[i])\n",
    "        res = []\n",
    "        for i in dd.keys():\n",
    "            dd[i].sort()\n",
    "            res += dd[i][-useLimit:]\n",
    "        res.sort()\n",
    "        return sum(res[-numWanted:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values, labels, numWanted, useLimit):\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: values[i], reverse=True)\n",
    "        mp = {}\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            p = idx[i]\n",
    "            if mp.get(labels[p], 0) >= useLimit:\n",
    "                continue\n",
    "            res += values[p]\n",
    "            mp[labels[p]] = mp.get(labels[p], 0) + 1\n",
    "            cnt += 1\n",
    "            if cnt >= numWanted:\n",
    "                break\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans = 0\n",
    "        numCount = 0\n",
    "        labelCount = dict()\n",
    "        for i in range(0, len(values)):\n",
    "            value = values[i]\n",
    "            label = labels[i]\n",
    "            if label in labelCount:\n",
    "                label_lst = labelCount[label]\n",
    "                if len(label_lst) < useLimit:\n",
    "                    ans = max(ans, ans+value)\n",
    "                    numCount += 1\n",
    "                    label_lst.append(value)\n",
    "                else:\n",
    "                    if value > label_lst[0]:\n",
    "                        ans = ans - label_lst[0] + value\n",
    "                        label_lst[0] = value\n",
    "                label_lst.sort()\n",
    "            else:\n",
    "                ans = max(ans, ans+value)\n",
    "                numCount += 1\n",
    "                labelCount[label] = [value]\n",
    "        ans_lst = []\n",
    "        for lst in labelCount.values():\n",
    "            ans_lst.extend(lst)\n",
    "        ans_lst.sort()\n",
    "        return sum(ans_lst[-numWanted:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        def quicksort(l,label,left,right):\n",
    "            if left>=right:\n",
    "                return l,label \n",
    "            i=left\n",
    "            j=right\n",
    "            v=l[left]\n",
    "            lab=label[left]\n",
    "\n",
    "            while i<j:\n",
    "                while i<j and l[j]<=v:\n",
    "                    j-=1\n",
    "                l[i]=l[j]\n",
    "                label[i]=label[j]\n",
    "\n",
    "                while i<j and l[i]>=v:\n",
    "                    i+=1\n",
    "                l[j]=l[i]\n",
    "                label[j]=label[i]\n",
    "            l[j]=v\n",
    "            label[j]=lab\n",
    "\n",
    "            l,label=quicksort(l,label,left,j-1)\n",
    "            l,label=quicksort(l,label,j+1,right)\n",
    "            return l,label\n",
    "        \n",
    "        d=dict()\n",
    "        for i in labels:\n",
    "            if i not in d.keys():\n",
    "                d[i]=0\n",
    "        \n",
    "        v,l=quicksort(values,labels,0,len(values)-1)\n",
    "        print(v,l)\n",
    "        \n",
    "        result=0\n",
    "        j=0\n",
    "        for i in range(len(values)):\n",
    "            if j>=numWanted:\n",
    "                break\n",
    "            if d[l[i]]<useLimit:\n",
    "                result+=v[i]\n",
    "                d[l[i]]+=1\n",
    "                j+=1\n",
    "        \n",
    "        return result\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, vs: List[int], ls: List[int], numWanted: int, useLimit: int) -> int:        \n",
    "        n = len(vs)\n",
    "        ids=list(range(n))\n",
    "        ids.sort(key=lambda x:vs[x], reverse=True)\n",
    "        ans=0\n",
    "        book=defaultdict(int)\n",
    "        for i in ids:\n",
    "            if book[ls[i]]<useLimit:\n",
    "                book[ls[i]] += 1\n",
    "                ans += vs[i]\n",
    "                numWanted -= 1\n",
    "                if not numWanted:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        map = {}\n",
    "        n = len(values)\n",
    "        for i in range(n):\n",
    "            if map.get(labels[i]) is None:\n",
    "                map[labels[i]] = [values[i]]\n",
    "            else:\n",
    "                if useLimit == len(map[labels[i]]):\n",
    "                    min_value = min(map[labels[i]])\n",
    "                    if min_value < values[i]:\n",
    "                        map[labels[i]].remove(min_value)\n",
    "                        map[labels[i]].append(values[i])\n",
    "                else:\n",
    "                    map[labels[i]].append(values[i])\n",
    "        arr = []\n",
    "        for v in map.values():\n",
    "            arr.extend(v)\n",
    "        arr.sort()\n",
    "        return sum(arr[-1 * numWanted:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        idx_sorted_by_values = sorted(list(range(len(values))), key=lambda idx : values[idx], reverse=True)\n",
    "        rtn = 0\n",
    "        idx_in_sorted_idx_lst = 0\n",
    "        collected_label = defaultdict(int)\n",
    "        while numWanted:\n",
    "            if idx_in_sorted_idx_lst >= len(values):\n",
    "                break\n",
    "            if collected_label[labels[idx_sorted_by_values[idx_in_sorted_idx_lst]]] < useLimit:\n",
    "                rtn += values[idx_sorted_by_values[idx_in_sorted_idx_lst]]\n",
    "                # collected_label.add(labels[idx_sorted_by_values[0]])\n",
    "                collected_label[labels[idx_sorted_by_values[idx_in_sorted_idx_lst]]] += 1\n",
    "                numWanted -= 1\n",
    "            idx_in_sorted_idx_lst += 1\n",
    "        return rtn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        s = sorted(zip(labels,values))\n",
    "        s = s[::-1]\n",
    "        a = []\n",
    "        i1 = -1\n",
    "        for i,j in s:\n",
    "            if i == i1:\n",
    "                if n > 0:\n",
    "                    a.append(j)\n",
    "                    n -= 1\n",
    "            else:\n",
    "                n = useLimit - 1\n",
    "                i1 = i\n",
    "                a.append(j)\n",
    "        a.sort(reverse = True)\n",
    "        return sum(a[0:numWanted])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        N = len(values)\n",
    "        sort_idx = sorted(range(N),key = lambda x: values[x], reverse = True)\n",
    "        d = defaultdict(int)\n",
    "        idx = 0\n",
    "        res = 0\n",
    "        while numWanted:\n",
    "            while idx < N and d[labels[sort_idx[idx]]] >= useLimit:\n",
    "                idx += 1\n",
    "            if idx == N:\n",
    "                break\n",
    "            d[labels[sort_idx[idx]]] += 1\n",
    "            res += values[sort_idx[idx]]\n",
    "            numWanted -= 1\n",
    "            idx += 1\n",
    "        #     print(d)\n",
    "        # print(d)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n=len(values)\n",
    "        limit={}\n",
    "        index=[i for i in range(n)]\n",
    "        ans=0\n",
    "        index.sort(key=lambda x:values[x],reverse=True)\n",
    "        print(index)\n",
    "        i=0\n",
    "        while i<n and numWanted>0:\n",
    "            label=labels[index[i]]\n",
    "            if limit.get(label,0)<useLimit:\n",
    "                limit[label]=limit.get(label,0)+1\n",
    "                ans+=values[index[i]]\n",
    "                numWanted-=1\n",
    "            i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        s = sorted(zip(labels,values))\n",
    "        s = s[::-1]\n",
    "        a = []\n",
    "        i1 = -1\n",
    "        for i,j in s:\n",
    "            if i == i1:\n",
    "                if n > 0:\n",
    "                    a.append(j)\n",
    "                    n -= 1\n",
    "            else:\n",
    "                n = useLimit - 1\n",
    "                i1 = i\n",
    "                a.append(j)\n",
    "        a.sort(reverse = True)\n",
    "        return sum(a[0:numWanted])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "\n",
    "        ans=0\n",
    "        k=0\n",
    "        dl={str(i):0 for i in labels}\n",
    "        while k<numWanted:\n",
    "            mv=max(values)\n",
    "            i=values.index(mv)\n",
    "            mv=values.pop(i)\n",
    "            ml=labels.pop(i)\n",
    "            if dl[str(ml)]<useLimit:\n",
    "                ans+=mv\n",
    "                dl[str(ml)]+=1\n",
    "        \n",
    "                k+=1\n",
    "            if values==[]:\n",
    "                break\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        di = {}\n",
    "        for i in range(len(values)):\n",
    "            if di.get(labels[i]):\n",
    "                di[labels[i]].append(values[i])\n",
    "            else:\n",
    "                di[labels[i]] = [values[i]]\n",
    "        ll = []\n",
    "        for i in di.keys():\n",
    "            di[i].sort()\n",
    "            ll += di[i][-useLimit:]\n",
    "        if len(ll) <= numWanted:\n",
    "            return sum(ll)\n",
    "        else:\n",
    "            ll.sort(reverse=True)\n",
    "            return sum(ll[: numWanted])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(labels)):\n",
    "            if labels[i] in dic:\n",
    "                dic[labels[i]].append(values[i])\n",
    "            else:\n",
    "                dic[labels[i]] = [values[i]]\n",
    "        res = [dic[i] for i in dic]\n",
    "        ans = []\n",
    "        for i in res:\n",
    "            i.sort(reverse = True)\n",
    "            if len(i) <= useLimit:\n",
    "                ans += i\n",
    "            else:\n",
    "                ans += [i[j] for j in range(useLimit)]\n",
    "        ans.sort(reverse = True)\n",
    "        return sum(ans[:numWanted])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''dic = {}\n",
    "        for i in range(len(labels)):\n",
    "            if labels[i] in dic:\n",
    "                dic[labels[i]] .append(values[i])\n",
    "            else:\n",
    "                dic[labels[i]] = [values[i]]\n",
    "        res =[[dic[i]] for i in dic]\n",
    "        res.sort(reverse = True)\n",
    "            \n",
    "        ans = []\n",
    "        for i in res :\n",
    "            if len(res) <=useLimit:\n",
    "                ans+=[j for j in i]\n",
    "            else:\n",
    "                ans+=[i[j] for j in range(useLimit)]\n",
    "        ans.sort(reverse = True)\n",
    "        return sum([ans[i] for i in range(numWanted)])'''\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "        '''vl = []\n",
    "        for i in range(len(labels)):\n",
    "            if labels[i] in vl:'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        dic = collections.defaultdict(list)\n",
    "        ret = []\n",
    "        for i in range(len(values)):\n",
    "            dic[labels[i]].append(values[i])\n",
    "        for label, value in dic.items():\n",
    "            ret += sorted(value)[-useLimit:]\n",
    "        return sum(sorted(ret)[-numWanted:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        if numWanted == 1:\n",
    "            return max(values)\n",
    "        label_2_values = {}\n",
    "        for i in range(len(values)):\n",
    "            if labels[i] in label_2_values:\n",
    "                label_2_values[labels[i]].append(values[i])\n",
    "            else:\n",
    "                label_2_values[labels[i]] = [values[i]]\n",
    "        print(label_2_values)\n",
    "        for label, values in label_2_values.items():\n",
    "            label_2_values[label] = sorted(label_2_values[label], reverse=True)[:useLimit]\n",
    "        \n",
    "        heap = []\n",
    "        res = 0\n",
    "        for label, values in label_2_values.items():\n",
    "            for v in values:\n",
    "                if len(heap) < numWanted:\n",
    "                    heapq.heappush(heap, v)\n",
    "                    res += v\n",
    "                else:\n",
    "                    if v > heap[0]:\n",
    "                        res -= heapq.heappop(heap)\n",
    "                        res += v\n",
    "                        heapq.heappush(heap, v)\n",
    "        print(label_2_values)\n",
    "        print(heap)\n",
    "        return res\n",
    "\n",
    "        \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key = lambda i: -values[i])\n",
    "\n",
    "        ans = choose = 0\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            label = labels[idx[i]]\n",
    "            if cnt[label] == useLimit:\n",
    "                continue\n",
    "            else:\n",
    "                choose += 1\n",
    "                ans += values[idx[i]]\n",
    "                cnt[label] += 1\n",
    "            if choose == numWanted:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        val_lab = []\n",
    "        n = len(values)\n",
    "        for i in range(n):\n",
    "            val_lab.append((values[i], labels[i]))\n",
    "        val_lab.sort(key = lambda x:x[0], reverse = True)\n",
    "        ans = val_lab[0][0]\n",
    "        lab = [val_lab[0][1]]\n",
    "        flag = 1\n",
    "        for j in range(1, n):\n",
    "            if flag == numWanted:\n",
    "                return ans\n",
    "            if lab.count(val_lab[j][1]) < useLimit:\n",
    "                lab.append(val_lab[j][1])\n",
    "                ans += val_lab[j][0]\n",
    "                flag += 1\n",
    "            else:\n",
    "                continue\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        data = []\n",
    "        for val, label in zip(values, labels):\n",
    "            data.append([val, label])\n",
    "        \n",
    "        data = sorted(data, key=lambda x:x[0], reverse=True)\n",
    "        # 总共拿numWante个，每种使用的uselimit。\n",
    "        vis = [0 ]* (max(labels)+1)\n",
    "        ans = 0\n",
    "        for i in range(len(data)):\n",
    "            # 可以拿不可以\n",
    "            if vis[data[i][1]] < useLimit:\n",
    "                ans+=data[i][0]\n",
    "                vis[data[i][1]]+=1\n",
    "                numWanted-=1\n",
    "                if numWanted == 0:\n",
    "                    return ans\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        h = []\n",
    "        for i in range(len(values)):\n",
    "            heapq.heappush(h, (-values[i], labels[i]))\n",
    "        res = [useLimit] * (max(labels) + 1)\n",
    "        ans = 0\n",
    "        cnt = numWanted\n",
    "        while cnt and h:\n",
    "            v, l = heapq.heappop(h)\n",
    "            v *= -1\n",
    "            if res[l] != 0:\n",
    "                ans += v\n",
    "                res[l] -= 1\n",
    "                cnt -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        idx=list(range(len(values)))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "        count=0\n",
    "        num=0\n",
    "        dic={}\n",
    "        for i in idx:\n",
    "            if numWanted==num:\n",
    "                break\n",
    "            if labels[i] not in dic.keys():\n",
    "                count+=values[i]\n",
    "                num+=1\n",
    "                dic[labels[i]]=1\n",
    "            elif dic[labels[i]]<useLimit:\n",
    "                num+=1\n",
    "                count+=values[i]\n",
    "                dic[labels[i]]+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "        print(idx)\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        mp = {}\n",
    "\n",
    "        for i in idx:\n",
    "            if count < numWanted:\n",
    "                mp[labels[i]] = mp.get(labels[i], 0) + 1\n",
    "                if mp[labels[i]] <= useLimit:\n",
    "                    ans += values[i]\n",
    "                    count += 1\n",
    "\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "        ans = choose = 0\n",
    "        cnt= Counter()\n",
    "        for i in range(n):\n",
    "            label = labels[idx[i]]\n",
    "            if cnt[label] == useLimit:\n",
    "                continue\n",
    "\n",
    "            choose += 1\n",
    "            ans += values[idx[i]]\n",
    "            cnt[label] += 1\n",
    "            if choose == numWanted:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        '''\n",
    "        idx的这个操作值得学习\n",
    "        '''\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        mp = {}\n",
    "\n",
    "        for i in idx:\n",
    "            if count < numWanted:\n",
    "                mp[labels[i]] = mp.get(labels[i], 0) + 1\n",
    "                if mp[labels[i]] <= useLimit:\n",
    "                    ans += values[i]\n",
    "                    count += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "\n",
    "        ans = choose = 0\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            label = labels[idx[i]]\n",
    "            if cnt[label] == useLimit:\n",
    "                continue;\n",
    "            \n",
    "            choose += 1\n",
    "            ans += values[idx[i]]\n",
    "            cnt[label] += 1\n",
    "            if choose == numWanted:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = [i for i in range(n)]\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "        ans = choose = 0\n",
    "        cnt = {}\n",
    "        i = 0\n",
    "        while(choose<numWanted and i < n):\n",
    "            if labels[idx[i]] not in cnt:\n",
    "                cnt[labels[idx[i]]] = 1\n",
    "            else:\n",
    "                cnt[labels[idx[i]]] += 1\n",
    "            if cnt[labels[idx[i]]] > useLimit:\n",
    "                i += 1\n",
    "                continue\n",
    "            ans += values[idx[i]]\n",
    "            choose += 1\n",
    "            i += 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n=len(values)\n",
    "        stuff=[]\n",
    "        for i in range(n):\n",
    "            stuff.append([values[i],labels[i]])\n",
    "        stuff.sort(key=lambda x:-x[0])\n",
    "        sign=[0]*(20001)\n",
    "        ans=0\n",
    "        num=0\n",
    "        for i,x in stuff:\n",
    "            if num<numWanted:\n",
    "                if sign[x]+1<=useLimit:\n",
    "                    ans+=i\n",
    "                    num+=1\n",
    "                    sign[x]+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i]) #idx存储的是索引号， 按values值的由大到小的顺序排列\n",
    "\n",
    "        ans = choose = 0\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            label = labels[idx[i]]\n",
    "            if cnt[label] == useLimit:\n",
    "                continue\n",
    "            \n",
    "            choose += 1\n",
    "            ans += values[idx[i]]\n",
    "            cnt[label] += 1\n",
    "            if choose == numWanted:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "\n",
    "        ans = choose = 0\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            label = labels[idx[i]]\n",
    "            if cnt[label] == useLimit:\n",
    "                continue\n",
    "            \n",
    "            choose += 1\n",
    "            ans += values[idx[i]]\n",
    "            cnt[label] += 1\n",
    "            if choose == numWanted:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "        choose = 0\n",
    "        dic = dict()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dic[labels[idx[i]]] = dic.get(labels[idx[i]],0)\n",
    "            if dic[labels[idx[i]]] >=useLimit:\n",
    "                continue\n",
    "            else:\n",
    "                dic[labels[idx[i]]] += 1\n",
    "                res += values[idx[i]]\n",
    "                choose += 1\n",
    "            if choose==numWanted:\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        idx = [i for i in range(len(values))]\n",
    "        idx.sort(key = lambda i: -values[i])\n",
    "\n",
    "        res = 0\n",
    "        dictv = {}\n",
    "        numw = 0\n",
    "        for i in idx:\n",
    "            if numw == numWanted:\n",
    "                break\n",
    "            if labels[i] not in dictv.keys():\n",
    "                dictv[labels[i]] = 1\n",
    "                res += values[i]\n",
    "                numw += 1\n",
    "            else:\n",
    "                if dictv[labels[i]] < useLimit:\n",
    "                    dictv[labels[i]] += 1\n",
    "                    res += values[i]\n",
    "                    numw += 1\n",
    "            print(res)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "\n",
    "        ans = choose = 0\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            label = labels[idx[i]]\n",
    "            if cnt[label] == useLimit:\n",
    "                continue;\n",
    "            \n",
    "            choose += 1\n",
    "            ans += values[idx[i]]\n",
    "            cnt[label] += 1\n",
    "            if choose == numWanted:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i: -values[i])\n",
    "\n",
    "        ans = choose = 0\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            label = labels[idx[i]]\n",
    "            if cnt[label] == useLimit:\n",
    "                continue;\n",
    "            \n",
    "            choose += 1\n",
    "            ans += values[idx[i]]\n",
    "            cnt[label] += 1\n",
    "            if choose == numWanted:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans=num=0\n",
    "        dic=Counter()\n",
    "        for k,v in sorted(zip(values,labels),reverse=True):\n",
    "            if dic[v]<useLimit:\n",
    "                dic[v]+=1\n",
    "                ans+=k\n",
    "                num+=1\n",
    "                if num==numWanted:\n",
    "                    break\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        tabel = list(map(list,zip(*[values,labels])))\n",
    "        tabel.sort(reverse=True)\n",
    "        # print(tabel[0][0])\n",
    "        d = dict()\n",
    "        res,i= [],0\n",
    "        while len(res) < numWanted and i < len(tabel):\n",
    "            if tabel[i][1] in d and d[tabel[i][1]] < useLimit:\n",
    "                res.append(tabel[i][0])\n",
    "                d[tabel[i][1]] += 1\n",
    "            if tabel[i][1] not in d:\n",
    "                res.append(tabel[i][0])\n",
    "                d[tabel[i][1]] = 1\n",
    "            i += 1\n",
    "        # print(res)\n",
    "        return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans = num = 0\n",
    "        cnt = Counter()\n",
    "        for v, l in sorted(zip(values, labels), reverse=True):\n",
    "            if cnt[l] < useLimit:\n",
    "                cnt[l] += 1\n",
    "                num += 1\n",
    "                ans += v\n",
    "                if num == numWanted:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans=num=0\n",
    "        c=Counter()\n",
    "        for v,l in sorted(zip(values,labels),reverse=True):\n",
    "            if c[l]<useLimit:\n",
    "                c[l]+=1\n",
    "                num+=1\n",
    "                ans+=v\n",
    "                if num==numWanted:\n",
    "                    break\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # from collections import Counter\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans = num = 0\n",
    "        cnt = Counter()\n",
    "        for v, l in sorted(zip(values, labels), reverse=True):\n",
    "            if cnt[l] < useLimit:\n",
    "                cnt[l] += 1\n",
    "                num += 1\n",
    "                ans += v\n",
    "                if num == numWanted:\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        pair = sorted(zip(values, labels), key = lambda x:-x[0]) # 首先排序\n",
    "\n",
    "        cnt = collections.defaultdict(int)\n",
    "        res = 0\n",
    "        for values, label in pair:\n",
    "            if numWanted>0:\n",
    "                if cnt.get(label, 0)<useLimit:\n",
    "                    cnt[label]+=1\n",
    "                    res+=values\n",
    "                    numWanted-=1\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        sorted_vl = sorted(zip(values, labels), reverse=True)\n",
    "        # print(sorted_vl)\n",
    "        n = len(sorted_vl)\n",
    "\n",
    "        label_cnt = defaultdict(int)\n",
    "        ans, cnt = 0, 0\n",
    "        for v, l in sorted_vl:\n",
    "            if label_cnt[l] >= useLimit:\n",
    "                continue\n",
    "            \n",
    "            ans += v\n",
    "            cnt += 1\n",
    "            label_cnt[l] += 1\n",
    "\n",
    "            if cnt >= numWanted: break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        # 题意: \n",
    "        # 相同标签的数字,最多选择useLimit个, 选择最大的前numWanted个数字, 返回它们的和\n",
    "\n",
    "        used = defaultdict(int)  # {label: used cnt}\n",
    "        ans = 0\n",
    "        for val, lab in sorted(zip(values, labels), reverse=True):\n",
    "            if used[lab] < useLimit:\n",
    "                ans += val\n",
    "                used[lab] += 1\n",
    "                numWanted -= 1\n",
    "            if not numWanted:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans = num = 0\n",
    "        cnt = collections.Counter()\n",
    "        for v, l in sorted(zip(values, labels), reverse=True):\n",
    "            if cnt[l] < useLimit:\n",
    "                cnt[l] += 1\n",
    "                num += 1\n",
    "                ans += v\n",
    "                if num == numWanted:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        res = 0\n",
    "        cnt = defaultdict(int)\n",
    "        num = 0\n",
    "        for v, l in sorted(zip(values, labels), reverse=True):\n",
    "            if num >= numWanted:\n",
    "                break\n",
    "\n",
    "            if cnt[l] < useLimit:\n",
    "                res += v\n",
    "                cnt[l] += 1\n",
    "                num += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans, num = 0, 0\n",
    "        count = Counter()\n",
    "        for v, l in sorted(zip(values, labels), reverse=True):\n",
    "            if count[l] < useLimit:\n",
    "                count[l] += 1\n",
    "                num += 1\n",
    "                ans += v\n",
    "                if num == numWanted:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq \n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        cnt=collections.Counter()\n",
    "        heap=[]\n",
    "        n=len(values)\n",
    "        for i in range(n):\n",
    "            heap.append([values[i],labels[i]])\n",
    "        total=0\n",
    "        cur=0\n",
    "        heap.sort(reverse=True)\n",
    "        for i in range(n):\n",
    "            if total==numWanted:\n",
    "                break\n",
    "            v=heap[i][0]\n",
    "            kind=heap[i][1]\n",
    "            if cnt[kind]<useLimit:\n",
    "                cnt[kind]+=1\n",
    "                cur+=v \n",
    "                total+=1\n",
    "\n",
    "        return cur \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        items = sorted(list(zip(values, labels)), key=lambda x: -x[0])\n",
    "        ans = 0\n",
    "        cnt1 = 0\n",
    "        cnt2 = collections.defaultdict(int)\n",
    "        for value, label in items:\n",
    "            cnt2[label] += 1\n",
    "            if cnt2[label] > useLimit:\n",
    "                continue\n",
    "            ans += value\n",
    "            cnt1 += 1\n",
    "            if cnt1 == numWanted:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        pair = sorted(zip(values, labels), key = lambda kv: -kv[0])\n",
    "        cnt = collections.defaultdict(int)\n",
    "        res = 0\n",
    "        for value, label in pair:\n",
    "            if numWanted > 0:\n",
    "                if cnt.get(label, 0) < useLimit:\n",
    "                    cnt[label] += 1\n",
    "                    res += value\n",
    "                    numWanted -= 1\n",
    "            else:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        resort_val = sorted( zip(values,labels) , key = lambda x:-x[0] )\n",
    "        label_cnt = collections.defaultdict(int)\n",
    "        res = 0\n",
    "        for val,lab in resort_val:\n",
    "            if numWanted == 0:   #取到足够多数量\n",
    "                break\n",
    "            if label_cnt[ lab ] < useLimit:\n",
    "                res += val\n",
    "                numWanted -= 1\n",
    "                label_cnt[lab] += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        values_lablesdict=[]\n",
    "        for values,labels in zip(values,labels):\n",
    "            values_lablesdict.append((values,labels))\n",
    "        \n",
    "        values_lableslist = sorted(values_lablesdict,key=lambda item:item[0],reverse=True)\n",
    "        count = {}\n",
    "        result = []\n",
    "        for item in values_lableslist:\n",
    "            if len(result) >= numWanted:\n",
    "                break\n",
    "            if item[1] not in count:\n",
    "                count[item[1]] = 0\n",
    "            if count[item[1]] < useLimit and len(result)< numWanted:\n",
    "                result.append(item[0])\n",
    "                count[item[1]] = count[item[1]] + 1\n",
    "        \n",
    "        return sum(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        nums = [[v,l] for v,l in zip(values, labels)]\n",
    "        nums.sort(key=lambda x:-x[0])\n",
    "        mapping = {}\n",
    "        nums_cnt = 0\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            v, l = nums[i]\n",
    "            if(l not in mapping):\n",
    "                mapping[l] = 1\n",
    "                result += v\n",
    "                nums_cnt += 1\n",
    "            else:\n",
    "                if(mapping[l] < useLimit):\n",
    "                    mapping[l] += 1\n",
    "                    result += v \n",
    "                    nums_cnt += 1\n",
    "                else:\n",
    "                    continue\n",
    "            if(nums_cnt == numWanted):\n",
    "                return result\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(\n",
    "        self, values: List[int], labels: List[int], numWanted: int, useLimit: int\n",
    "    ) -> int:\n",
    "        ans = k = 0\n",
    "        cnt = Counter()\n",
    "        nums = list(zip(values, labels))\n",
    "        nums = sorted(nums, key = lambda x: x[0], reverse = True)\n",
    "\n",
    "        for value, label in nums:\n",
    "            \n",
    "            if cnt[label] < useLimit:\n",
    "                cnt[label] += 1\n",
    "                ans += value\n",
    "                k += 1\n",
    "\n",
    "            if k == numWanted:\n",
    "                break\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        cup = [[val,lab] for val,lab in zip(values,labels)]\n",
    "        cup.sort(reverse = True,key = lambda x:x[0])\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        #存储标签使用次数\n",
    "        dic = {}\n",
    "        for x in labels:\n",
    "            dic[x] = 0\n",
    "        for val,lab in cup:\n",
    "            if dic[lab]<useLimit:\n",
    "                ans += val\n",
    "                dic[lab] += 1\n",
    "                count += 1\n",
    "            else:\n",
    "                continue\n",
    "            if count==numWanted:\n",
    "                break\n",
    "        print(cup)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        res=[]\n",
    "        for i in range(len(values)):\n",
    "            res.append((values[i],labels[i]))\n",
    "        res=sorted(res,key=lambda x:-x[0])\n",
    "        max1=0\n",
    "        d=collections.defaultdict(int)\n",
    "        count=0\n",
    "        for v,l in res:\n",
    "            if count<numWanted:  \n",
    "                if d[l]+1<=useLimit:\n",
    "                    d[l]+=1\n",
    "                    max1+=v\n",
    "                    count+=1\n",
    "        return max1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "\n",
    "        # print(zip(values, labels))\n",
    "\n",
    "        lenl = len(values)\n",
    "\n",
    "        cm = []\n",
    "\n",
    "        for i in range(lenl):\n",
    "            cm.append([values[i], labels[i]])\n",
    "\n",
    "        cm.sort(key=lambda x: -x[0])\n",
    "\n",
    "        # print(cm)\n",
    "\n",
    "        out = 0\n",
    "\n",
    "        st = 0\n",
    "\n",
    "        dct = {}\n",
    "\n",
    "        for _ in range(numWanted):\n",
    "\n",
    "            \n",
    "            inputing = True\n",
    "\n",
    "            while inputing and st < lenl:\n",
    "                nm = cm[st][0]\n",
    "                lb = cm[st][1]\n",
    "\n",
    "\n",
    "                if lb in dct:\n",
    "                    if dct[lb] < useLimit:\n",
    "                        out += nm\n",
    "                        dct[lb] += 1\n",
    "                        inputing = False\n",
    "                        \n",
    "                    # else:\n",
    "                    #     st += 1\n",
    "\n",
    "\n",
    "                else:\n",
    "                    dct[lb] = 1\n",
    "                    out += nm\n",
    "                    inputing = False\n",
    "                \n",
    "                st += 1\n",
    "            \n",
    "        return out\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        nums = [[v,l] for v,l in zip(values, labels)]\n",
    "        nums.sort(key=lambda x:-x[0])\n",
    "        mapping = {}\n",
    "        nums_cnt = 0\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            v, l = nums[i]\n",
    "            if(l not in mapping):\n",
    "                mapping[l] = 1\n",
    "                result += v\n",
    "                nums_cnt += 1\n",
    "            else:\n",
    "                if(mapping[l] < useLimit):\n",
    "                    mapping[l] += 1\n",
    "                    result += v \n",
    "                    nums_cnt += 1\n",
    "                else:\n",
    "                    continue\n",
    "            if(nums_cnt == numWanted):\n",
    "                return result\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        d = [[key,value] for key,value in zip(values,labels)]\n",
    "        m = sorted(d,key=lambda x:-x[0])\n",
    "        result = 0\n",
    "        p = {}\n",
    "        k = 0\n",
    "        for key,value in m:\n",
    "            if k == numWanted:\n",
    "                break\n",
    "            if value not in p.keys():\n",
    "                p[value] = 1\n",
    "                result += key\n",
    "                k += 1\n",
    "            else:\n",
    "                if p[value] < useLimit:\n",
    "                    p[value] += 1\n",
    "                    result += key\n",
    "                    k += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        # label_dict = defaultdict(list)\n",
    "        # for v, l in zip(values, labels):\n",
    "        #     label_dict[l].append(v)\n",
    "        # for k in label_dict.keys():\n",
    "        #     label_dict[k].sort(reverse=True)\n",
    "        label_cnt = {}\n",
    "        for l in labels:\n",
    "            label_cnt[l] = useLimit\n",
    "        v_l = [(v,l) for v, l in zip(values, labels)]\n",
    "        v_l.sort(key=lambda x: x[0], reverse=True)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        print(v_l)\n",
    "        print(label_cnt)\n",
    "        while numWanted > 0 and i < len(values):\n",
    "            v = v_l[i][0]\n",
    "            l = v_l[i][1]\n",
    "            if label_cnt[l] > 0:\n",
    "                res += v\n",
    "                label_cnt[l] -= 1\n",
    "                numWanted -= 1\n",
    "            \n",
    "            i += 1\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        vl = [[values[_], labels[_]] for _ in range(len(values))]\n",
    "        num_cnt = {lab: useLimit for lab, _ in Counter(labels).items()}\n",
    "        vl.sort(reverse = True)\n",
    "        score = 0\n",
    "        for i in range(len(values)):\n",
    "            if num_cnt[vl[i][1]] == 0:\n",
    "                continue\n",
    "            # print(vl[i][0], vl[i][1])\n",
    "            num_cnt[vl[i][1]] -= 1\n",
    "            score += vl[i][0]\n",
    "            numWanted -= 1\n",
    "            if numWanted == 0:\n",
    "                break\n",
    "        return score\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        arr = [[values[i], labels[i]] for i in range(n)]\n",
    "        arr.sort(key = lambda x: -x[0])\n",
    "        ans = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if total >= numWanted: break\n",
    "            if d[arr[i][1]] + 1 > useLimit: continue\n",
    "            d[arr[i][1]] += 1\n",
    "            ans += arr[i][0]\n",
    "            total += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        \"\"\"\n",
    "        对values从大到小排序 显然从大到小进行选择\n",
    "        \"\"\"\n",
    "        values, labels = zip(*sorted(zip(values, labels),reverse=True))\n",
    "        used = defaultdict(int)#记录每个类别用了几个\n",
    "        rs = 0\n",
    "        for i in range(len(values)):\n",
    "            if numWanted==0:\n",
    "                break\n",
    "            if used[labels[i]]<useLimit:\n",
    "                rs += values[i]\n",
    "                used[labels[i]] += 1\n",
    "                numWanted -= 1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        values_labels = []\n",
    "        for value, label in zip(values, labels):\n",
    "            values_labels.append([value, label])\n",
    "        values_labels.sort(key = lambda x: -x[0])\n",
    "        cnt = Counter()\n",
    "        ans, idx = 0,0\n",
    "        while numWanted and idx < len(values_labels):\n",
    "            if cnt[values_labels[idx][1]] < useLimit:\n",
    "                ans += values_labels[idx][0]\n",
    "                cnt[values_labels[idx][1]] += 1\n",
    "                numWanted -= 1\n",
    "            idx += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        count_hash = {}\n",
    "        result_list = []\n",
    "\n",
    "        for item in set(labels):\n",
    "            count_hash[item] = 0\n",
    "\n",
    "        for value,label in sorted(zip(values,labels),reverse=True):\n",
    "            if len(result_list) == numWanted:\n",
    "                break\n",
    "            if count_hash[label] < useLimit:\n",
    "                result_list.append(value)\n",
    "                count_hash[label] = count_hash[label] + 1\n",
    "            \n",
    "        \n",
    "        return sum(result_list)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        vl = [[values[_], labels[_]] for _ in range(len(values))]\n",
    "        num_cnt = {lab: useLimit for lab, _ in Counter(labels).items()}\n",
    "        vl.sort(reverse = True)\n",
    "        score = 0\n",
    "        for i in range(len(values)):\n",
    "            if num_cnt[vl[i][1]] == 0:\n",
    "                continue\n",
    "            # print(vl[i][0], vl[i][1])\n",
    "            num_cnt[vl[i][1]] -= 1\n",
    "            score += vl[i][0]\n",
    "            numWanted -= 1\n",
    "            if numWanted == 0:\n",
    "                break\n",
    "        return score\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        data = collections.defaultdict(int)\n",
    "        n = 0\n",
    "        d = [[v, k] for (v, k) in zip(values, labels)]\n",
    "        d = sorted(d, key=lambda x: -x[0])\n",
    "        res = 0\n",
    "        for v, k in d:\n",
    "            if data.get(k, 0) == useLimit:\n",
    "                continue\n",
    "            data[k] += 1\n",
    "            n += 1\n",
    "            res += v\n",
    "            if n == numWanted:\n",
    "                break\n",
    "        # print(data)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        vl = sorted(zip(values, labels), reverse=True)\n",
    "        new_values, new_labels = [list(x) for x in zip(*vl)]\n",
    "\n",
    "        res = 0\n",
    "        cnt = defaultdict(int)\n",
    "        num = 0\n",
    "        for i, v in enumerate(new_values):\n",
    "            if num >= numWanted:\n",
    "                break\n",
    "\n",
    "            if cnt[new_labels[i]] < useLimit:\n",
    "                res += v\n",
    "                cnt[new_labels[i]] += 1\n",
    "                num += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        n = len(values)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append([values[i], labels[i]])\n",
    "\n",
    "        res.sort(key = lambda x: -x[0])\n",
    "        \n",
    "        \n",
    "        d = dict.fromkeys([res[i][1] for i in range(n)], 0)\n",
    "        print(d)\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if cnt >= numWanted:\n",
    "                break\n",
    "            if d[res[i][1]] < useLimit:\n",
    "                ans += res[i][0]\n",
    "                cnt += 1\n",
    "                d[res[i][1]] +=1\n",
    "\n",
    "        return ans        \n",
    "\n",
    " \n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        import copy\n",
    "\n",
    "        global ltimes\n",
    "        n = len(values)\n",
    "        dic = {}\n",
    "        for i,j in zip(values, labels):\n",
    "            if i not in dic.keys():\n",
    "                dic[i] = [j]\n",
    "            else:\n",
    "                dic[i].append(j)\n",
    "\n",
    "\n",
    "        ltimes = {}\n",
    "        values.sort()\n",
    "        values.reverse()\n",
    "        selectlist = []\n",
    "        score = 0 \n",
    "        add = 0\n",
    "\n",
    "        times = 0\n",
    "        for i in range(n):\n",
    "            CorrespondingL = dic[values[i]]\n",
    "            for k in range(len(CorrespondingL)):\n",
    "                ll = CorrespondingL[k]\n",
    "                if ll not in ltimes.keys():\n",
    "                    ltimes[ll] = 1\n",
    "                    selectlist.append(values[i])\n",
    "                    score += values[i]\n",
    "                    times += 1\n",
    "                    del dic[values[i]][k]\n",
    "                    break\n",
    "                \n",
    "                elif ltimes[ll]<useLimit:\n",
    "                    selectlist.append(values[i])\n",
    "                    score += values[i]\n",
    "                    ltimes[ll] += 1\n",
    "                    times += 1\n",
    "                    del dic[values[i]][k]\n",
    "                    break\n",
    "            if times == numWanted:\n",
    "                break\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        ans = 0\n",
    "        dic = {}\n",
    "        values_s, labels_s = (list(t) for t in zip(*sorted(zip(values, labels), reverse=True)))\n",
    "        j = 0\n",
    "        for i in range(len(values)):\n",
    "            if j == numWanted:\n",
    "                break\n",
    "            if labels_s[i] not in dic:\n",
    "                ans += values_s[i]\n",
    "                dic[labels_s[i]] = 1\n",
    "                j += 1\n",
    "            else:\n",
    "                if dic[labels_s[i]] < useLimit:\n",
    "                    ans += values_s[i]\n",
    "                    dic[labels_s[i]] += 1\n",
    "                    j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        l = []\n",
    "        ans = 0\n",
    "        c = Counter(labels)\n",
    "        for i in range(len(values)):\n",
    "            heapq.heappush(l, (-values[i], labels[i]))\n",
    "        pick = defaultdict(int)\n",
    "        while numWanted > 0 and l:\n",
    "            value, label = heapq.heappop(l)\n",
    "            if pick[label] < useLimit and c[label] > 0:\n",
    "                c[label] -= 1\n",
    "                pick[label] += 1\n",
    "                ans += -value\n",
    "                numWanted -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        zip_a_b = zip(values,labels)\n",
    "        sorted_zip = sorted(zip_a_b, key=lambda x:x[0], reverse=True)\n",
    "        values, labels = map(list,zip(*sorted_zip))\n",
    "\n",
    "        ans = 0\n",
    "        used = {}\n",
    "        for v, l in zip(values,labels):\n",
    "            if numWanted == 0: break\n",
    "            if used.get(l,0) < useLimit:\n",
    "                ans += v\n",
    "                numWanted -= 1\n",
    "                used[l] = used.get(l,0) + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        value_label = sorted(list(zip(values, labels)), key=lambda x:x[0], reverse=True)\n",
    "\n",
    "        result_dict = defaultdict(list)\n",
    "        cnt = 0\n",
    "        index = 0\n",
    "\n",
    "        while index < len(value_label) and cnt < numWanted:\n",
    "            if len(result_dict[value_label[index][1]]) < useLimit:\n",
    "                result_dict[value_label[index][1]].append(value_label[index][0])\n",
    "                cnt += 1\n",
    "            index += 1\n",
    "            \n",
    "        return sum([sum(value) for key, value in result_dict.items()])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        label_cnt={}\n",
    "        cnt=0\n",
    "        i=0\n",
    "        ans=0\n",
    "        z=zip(values,labels)\n",
    "        z=sorted(z,reverse=True)\n",
    "        values,labels=zip(*z)\n",
    "        while cnt<numWanted:\n",
    "            if labels[i] not in label_cnt:\n",
    "                ans+=values[i]\n",
    "                label_cnt[labels[i]]=1\n",
    "                cnt+=1\n",
    "            elif label_cnt[labels[i]]<useLimit:\n",
    "                ans+=values[i]\n",
    "                label_cnt[labels[i]]+=1\n",
    "                cnt+=1\n",
    "            i+=1\n",
    "            if i==len(values):\n",
    "                break\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:\n",
    "        value_label = sorted(list(zip(values, labels)), key=lambda x:x[0], reverse=True)\n",
    "\n",
    "        result_dict = defaultdict(list)\n",
    "        cnt = 0\n",
    "        index = 0\n",
    "\n",
    "        while index < len(value_label) and cnt < numWanted:\n",
    "            if len(result_dict[value_label[index][1]]) < useLimit:\n",
    "                result_dict[value_label[index][1]].append(value_label[index][0])\n",
    "                cnt += 1\n",
    "            index += 1\n",
    "            \n",
    "        return sum([sum(value) for key, value in result_dict.items()])\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
